package com.star.niuke;

import java.util.*;

/**
 * @author: liminghui
 * @date: 2021/7/22 14:47
 * @version: 1.0
 * @description: NC93 设计LRU缓存结构 不完全对90%通过率
 * <p>
 * [[1,1,1],[1,2,2],[1,3,2],[2,1],[1,4,4],[2,2]],3
 * 二维数组中第0位即：[1,1,1]，第一个1表示opt=1，要set(1,1)，即要将(1,1)插入缓存
 * 二维数组中第1为即：[1,2,2]，第一个1表示opt=1，要set(2,2)，即要将(2,2)插入缓存
 * 二维数组中第2位即：[1,3,2]，第一个1表示opt=1，要set(3,2)，即要将(3,2)插入缓存
 * 二维数组中第3位即：[2,1]，第一个2表示opt=2，要get(1)，即从缓存中查找key为1的值，前面已经插入了key=1，所以返回1，这个要保存到返回数组中
 * 二维数组中第5位即：[2,2]，第一个2表示opt=2，要get(2)，即从缓存中查找key为2的值，由于缓存大小为3，所以前面插入的key=2已经被挤出缓存，所以返回结果为-1，这个要保存到返回数组中
 * 所以输出为[1,-1]
 * 示例1中，输入最后一个单独的3表示缓存大小
 */
public class LRU {

    public static void main(String[] args) {
        LRU lru = new LRU();
        int[][] operators = {{1, 1, 1}, {1, 2, 2}, {1, 3, 2}, {2, 1}, {1, 4, 4}, {2, 2}};
        int k = 3;
        int[] result = lru.lRU(operators, k);
        System.out.println(Arrays.toString(result));
    }

    /**
     * lru design
     *
     * @param operators int整型二维数组 the ops
     * @param k         int整型 the k
     * @return int整型一维数组
     */
    public int[] lRU(int[][] operators, int k) {
        // write code here
        Map<Integer, Integer> map = new LinkedHashMap<>(); //有序map
        List<Integer> list = new ArrayList<Integer>(); // 结果集合
        int len = (int) Arrays.stream(operators).filter(x -> x[0] == 2).count();
        int[] res = new int[len];
        int j = 0;
        for (int[] operator : operators) {
            int key = operator[1];
            int opt = operator[0]; // opt=1代表set(x,y) ,opt=2代表get(x)
            if (opt == 1) {
                int value = operator[2];
                if (map.size() < k) { // 判断map长度是否小于最大限制
                    map.put(key, value);
                } else {
                    map.remove(map.keySet().iterator().next()); //移除最久远的最开始0号元素
                    map.put(key, value);
                }
            } else if (opt == 2) { // get操作
                if (map.containsKey(key)) { // 包含 先移除在添加
                    Integer value = map.get(key);
                    map.remove(key);
                    map.put(key, value);
                    res[j++] = 1;
                } else {
                    res[j++] = -1;
                }
            }
        }


        return res;

    }
}
